package RushHour;
import java.util.HashSet;

/**
 * This is the template for a class that performs A* search on a given
 * rush hour puzzle with a given heuristic.  The main search
 * computation is carried out by the constructor for this class, which
 * must be filled in.  The solution (a path from the initial state to
 * a goal state) is returned as an array of <tt>State</tt>s called
 * <tt>path</tt> (where the first element <tt>path[0]</tt> is the
 * initial state).  If no solution is found, the <tt>path</tt> field
 * should be set to <tt>null</tt>.  You may also wish to return other
 * information by adding additional fields to the class.
 */
public class AStar {

    /** The solution path is stored here */
    public State[] path;
    public String[] moves;
    HashSet<State> closedList;
    HashSet<State> openListHashSet;
    FibonacciHeap<Node> openListHeap;
    double heuristicAvarage;
    double numOfHops;
    int minDepth, maxDepth, avgDepth;
    int numOfBranchChanges;
    
    /**
     * This is the constructor that performs A* search to compute a
     * solution for the given puzzle using the given heuristic.
     */
    public AStar(Puzzle puzzle, Heuristic heuristic, long timeoutMilisec) {
    	//Init
    	long startTime = System.currentTimeMillis();
    	Node goalStateNode = null;
    	closedList = new HashSet<State>();
    	openListHashSet = new HashSet<State>();
    	openListHeap = new FibonacciHeap<Node>();
    	heuristicAvarage = 0;
    	numOfHops = 0;
    	minDepth = Integer.MAX_VALUE;
    	maxDepth = Integer.MIN_VALUE;
    	avgDepth = 0;
    	numOfBranchChanges = 0;
    	goalStateNode = searchForSol(puzzle, heuristic, timeoutMilisec, startTime, goalStateNode);
    	//Found no solution...
    	if (goalStateNode == null)
    	{
    		path = null;
    		return;
    	}
    	buildSolutionPath(goalStateNode);
    }

	private Node searchForSol(Puzzle puzzle, Heuristic heuristic, 
			long timeoutMilisec, long startTime, Node goalStateNode) {
		//Step #1 in A* algo'
    	Node s = puzzle.getInitNode();
    	addNodeToOpenList(s, heuristic);
    	//Steps #2 to #7 in A* algo'
    	Node prevNode = null;
    	while (!openListHeap.isEmpty())
    	{
    		Node minNode = getMinStateNode();
    		//Check if we moved to a different branch
    		if (prevNode!= null && prevNode.getDepth() >= minNode.getDepth())
    		{
    			//Maintain stat
    			if (prevNode.getDepth() < minDepth)
    				minDepth = prevNode.getDepth();
    			if (prevNode.getDepth() > maxDepth)
    				maxDepth = prevNode.getDepth();
    			avgDepth += prevNode.getDepth();
    			numOfBranchChanges++;
    		}
    		if (minNode.getState().isGoal())//Found solution
    		{
    			goalStateNode = minNode;
    			if (prevNode == null || prevNode.getDepth() < minNode.getDepth())
    			{
    				//If this wasn't reached as a brach change
	    			if (minNode.getDepth() < minDepth)
	    				minDepth = minNode.getDepth();
	    			if (minNode.getDepth() > maxDepth)
	    				maxDepth = minNode.getDepth();
	    			avgDepth += minNode.getDepth();
	    			numOfBranchChanges++;
    			}
    			break;
    		}
    		//If not a goal node lets expand it...
    		Node[] sons = minNode.expand();
    		for (Node tmpNode : sons)
    		{
    			//Since our heuristic is consistent if we encounter
    			//an already seen state we can skip it since
    			//the new path is at least as expenssive as the previous
    			if (openListHashSet.contains(tmpNode.getState()) ||
    					closedList.contains(tmpNode.getState()))
    				continue;
    			//Add the node to the open list
    			addNodeToOpenList(tmpNode, heuristic);
    		}
    		if (System.currentTimeMillis()-startTime > timeoutMilisec)
    		{
    			path = null;
    			return null;
    		}
    		prevNode = minNode;
    	}
		return goalStateNode;
	}
    
    /**
     * Get the min (By it's f value) from the heap and manage the has sets
     * @return
     */
    private Node getMinStateNode()
    {
    	Node minNode = openListHeap.removeMin();
		openListHashSet.remove(minNode.getState());
		closedList.add(minNode.getState());
		return minNode;
    }
    
    /**
     * Adds the node to the open list data structrue
     * @param node
     * @return
     */
    private void addNodeToOpenList(Node node, Heuristic h)
    {
    	openListHashSet.add(node.getState());
    	openListHeap.insert(node,  calcF(node, h));
    }
    
    private int calcF(Node node, Heuristic h)
    {
    	int hVal = h.getValue(node.getState());
    	heuristicAvarage += hVal;
    	numOfHops++;
    	return  hVal+ node.getDepth();
    }
    
    public double getHeuristicAvarage()
    {
    	return heuristicAvarage / numOfHops;
    }
    
    /**
     * Retrace the solution path from the goal Node
     * @param goalStateNode
     */
    private void buildSolutionPath(Node goalStateNode)
    {
    	path = new State[goalStateNode.getDepth()];
    	moves = new String[goalStateNode.getDepth()];
    	Node pathIterator = goalStateNode;
    	for (int i=goalStateNode.getDepth(); i>0; i--)
    	{
    		path[i-1] = pathIterator.getState();
    		moves[i-1] = pathIterator.getState().reachedByMove;
    		pathIterator = pathIterator.getParent();
    	}
    }

	public double getAvgDepth() {
		return (double)avgDepth / (double)numOfBranchChanges;
	}

	public int getMaxDepth() {
		return maxDepth;
	}

	public int getMinDepth() {
		return minDepth;
	}   
}
